package 剑指offer_leetcode;

/**
 * JZ62孩子们的游戏_圆圈中最后剩下的数_
 */
public class 剑指Offer62_圆圈中最后剩下的数字 {

    //构造环形链表


    //递归
    /**
     * 找出 f(n,m) 与 f(n-1,m)的关系
     * f(n,m) 表示士兵个数为 n 时， 存活的士兵编号为 f(n,m)
     * new = (old + m ) % n
     * f(n,k) = (f(n-1,k) + m) % n
     */
    public int lastRemaining(int n, int m) {
        if(n==0)   return n;
//        return (lastRemaining(n-1,m) + m) % n;

        //优化
        int res = 1;
        for(int i =1; i<=n ; i++)
            res = (res + m) % i;
        return res;
    }
}
